// 基于CAS的无锁队列
// 先进先出（FIFO）

// 参考文献：
// Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
// Maged M. Michael, Michael L. Scott
// Department of Computer Science, University of Rochester
// https://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf

#include <stdatomic.h>
#include <stdlib.h>

#include "cas_queue.h"

q_node_t *init_node(q_node_t *n)
{
	if (n == NULL)
		n = (q_node_t *)malloc(sizeof(q_node_t));

	n->belong_queue = NULL;
	n->next = NULL;
	n->data = NULL;

	return n;
}

/**
 * @brief init a new queue
 *
 * @param q if =NULL will malloc space
 * @return q_queue_t*
 */
q_queue_t *q_init(q_queue_t *q)
{
	if (q == NULL)
		q = (q_queue_t *)malloc(sizeof(q_queue_t));

	q_node_t *dummy_node = init_node(NULL);

	dummy_node->next = NULL;
	dummy_node->belong_queue = q;
	q->head = dummy_node;
	q->tail = dummy_node;

	return q;
}

/**
 * @brief
 *
 * @param q
 * @param data pointer to store
 * @return int =0 ok
 */
int q_push(q_queue_t *q, void *data)
{
	q_node_t *n = init_node(NULL);
	n->data = data;
	n->next = NULL;
	n->belong_queue = q;

	q_node_t *tail, *next;

	while (1)
	{
		tail = q->tail;
		next = tail->next;
		if (tail != q->tail)
			continue;
		if (next != NULL)
		{
			atomic_compare_exchange_strong(&(q->tail), &tail, next);
			continue;
		}
		if (atomic_compare_exchange_strong(&(tail->next), &next, n))
			break;
	}
	atomic_compare_exchange_strong(&(q->tail), &tail, n);

	return 0;
}

/**
 * @brief
 *
 * @param q
 * @param data pointer of pointer, to get stored address
 * @return int =0 ok =-1 empty queue
 */
int q_pop(q_queue_t *q, void **data)
{
	q_node_t *head, *tail, *next;
	while (1)
	{
		head = q->head;
		tail = q->tail;
		next = head->next;

		if (head == q->head)
		{
			if (head == tail)
			{
				if (next == NULL)
					return -1;
				atomic_compare_exchange_strong(&(q->tail), &tail, next);
			}
			else
			{
				*data = next->data;
				if (atomic_compare_exchange_strong(&(q->head), &head, next))
					break;
			}
		}
	}
	free(head);
	// free
	return 0;
}
